package qunaer;

/**
 * @author Hang
 * @date 2022/9/7
 * @project AutumnOffer
 * @description
 **/
public class Solution1 {
    public static void main(String[] args) {
        int energy = 10;
        int[][] actions = new int[][]{{1,1},{2,3},{3,5},{5,10},{7,9},{8,10}};
        System.out.println(maxScore(energy, actions));
    }
    public static int maxScore (int energy, int[][] actions) {
        // write code here
        int[][] dp = new int[actions.length][energy+1];
        for(int j=actions[0][0];j<=energy;j++){
            dp[0][j] = actions[0][1];
        }
        for(int i=1;i<actions.length;i++){
            for(int j=0;j<=energy;j++){
                if(j-actions[i][0] < 0){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-actions[i][0]]+actions[i][1]);
                }
            }
        }
        return dp[actions.length-1][energy];
    }
}
